package strings;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

/**
 * @author pengfei.hpf
 * @date 2020/3/29
 * @verdion 1.0.0
 * 93. 复原IP地址
 * 给定一个只包含数字的字符串，复原它并返回所有可能的 IP 地址格式。
 *
 * 示例:
 *
 * 输入: "25525511135"
 * 输出: ["255.255.11.135", "255.255.111.35"]
 * 通过次数32,832提交次数71,089
 */
public class RestoreIpAddresses {

    List<String> res = new ArrayList<>();

    public List<String> restoreIpAddresses(String s) {
        if(s == null || s.length() == 0 || s.length() < 4 || s.length() > 12){
            return res;
        }
        backtrack(s, 0, new LinkedList<String>(), 0);
        return res;
    }

    private void backtrack(String s, int start, LinkedList<String> path, int pos){
        int rest = s.length() - start;
        if(pos == 4 && rest == 0){
            StringBuilder builder = new StringBuilder();
            for(String str: path){
                builder.append(str);
            }
            res.add(builder.toString());
            return;
        }

        if(rest < (4 - pos) || rest > (4-pos) * 3){
            return;
        }
        int end = 3;
        //TODO: 别忘了0开头的
        if(s.charAt(start) == '0'){
            end = 1;
        }
        for(int i = 1; i <=end; i ++){
            if(start + i > s.length()){
                break;
            }
            String cur = s.substring(start, start + i);
            if(Integer.parseInt(cur) <= 255){
                if(pos < 3){
                    cur = cur + ".";
                }
                path.add(cur);
                backtrack(s, start + i, path, pos + 1);
                path.removeLast();
            } else {
                break;
            }
        }
    }
}
